package primary.primary0;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 */
public class S0015三数之和 {

    /**
     * 看答案: 排序 + 双指针
     * 遍历3个位置的话需要N^3，但是如果先排序，在固定1，那么就是 nums[loc2] + numcs[loc3] = 固定值
     * 对于有序数组，这个可以用双指针
     * 假设我们要遍历所有loc2和loc3，loc2从loc1开始，loc3从n - 1开始
     * for loc2 xxxx for loc3 xxx 两层嵌套，找一个 nums[loc2] + numcs[loc3] = 固定值 的位置
     * 但是注意 如果有 nums[loc2] + numcs[loc3] < 固定值, 那么loc3就不用再往下移动了，因为后面的肯定不符合
     * 所以我们把 loc2++，但是注意nums[loc2]肯定比上一轮遍历大，所以对于 loc3 + 1 -> n - 1之间的loc3，肯定有 nums[loc2] + numcs[loc3] > 固定值
     * 所以loc3还是从loc3的位置开始跑，
     * 这就是双指针，在有序数组中，两个指针一起往中间跑
     */




    /**
     * 8.4，排序 + 双指针 + 二分查找
     */
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length < 3){
            return new ArrayList<List<Integer>>();
        }
        Arrays.sort(nums); // 由小到大
        int loc1 = 0;
        int loc2 = 0;
        List<List<Integer>> res = new ArrayList<>();
        for(loc1 = 0; loc1 < nums.length - 2; loc1 ++){
            // 要与上一个不同, 这样的话, 比如有一排0, 那么0在同一个位置只会出现一次, 不知道会不会漏。
            if(loc1 != 0 && nums[loc1] == nums[loc1 - 1]){
                continue;
            }
            for(loc2 = loc1 + 1; loc2 < nums.length - 1; loc2 ++){
                if(loc2 != loc1 + 1 && nums[loc2] == nums[loc2 - 1]){
                    continue;
                }
                int loc3 = Arrays.binarySearch(nums, loc2 + 1, nums.length, 0 - nums[loc1] - nums[loc2]);
                // int loc3 = Arrays.binarySearch(nums, 0 - nums[loc1] - nums[loc2]);
                // System.out.println("本次查找到的位置: " + loc3);
                if(loc3 > loc2){
                    addList(nums, loc1, loc2, loc3, res);
                }
            }
        }


        return res;
    }

    // 单个元组添加到res里
    private void addList(int[] nums, int loc1, int loc2, int loc3, List<List<Integer>> res){
        // 查看是不是和上一个一样
        // if(res.size() != 0){
        //     List<Integer> pre = res.get(res.size() - 1);
        //     if(pre.get(0).equals(nums[loc1]) && pre.get(1).equals(nums[loc2]) && pre.get(2).equals(nums[loc3])){
        //         return ;
        //     }
        // }
        List<Integer> resEle = new ArrayList<>();
        resEle.add(nums[loc1]);
        resEle.add(nums[loc2]);
        resEle.add(nums[loc3]);
        res.add(resEle);
    }
}
